package fingerprint;

import java.util.ArrayList;

/**
 * Created by 11956 on 2016/11/8.
 *
 */
public class FingerPrint {

    // DO NOT write FFT.WINDOW_SIZE / 44100, it equals to 0 forever!!
    public static final double scaling = FFT.WINDOW_SIZE / 44100.0;
    private static final int interval_num = 3;
    private static final int start_freq = 440;

    private ArrayList<int[]> constel_data = new ArrayList<>();
    private int id;

    private static final int[][] freqRanges = new int[interval_num][2];

    static {
        for (int i = 0; i < interval_num; ++i) {
            freqRanges[i][0] = (int) Math.round((start_freq << i) * scaling);
            freqRanges[i][1] = (int) Math.round((start_freq << (i + 1)) * scaling);
        }
    }

    /**
     * For songs about to add into DB
     * @param id
     */
    public FingerPrint(int id) {
        this.id = id;
    }

    /**
     * For songs about to be searched
     */
    public FingerPrint() {
        this.id = -1;
    }

    /**
     * Append a column of frequency peaks to the constellation map.
     * A frequency peak is a frequency value whose amplitude is the highest among
     * all frequencies in a frequency interval.
     *
     * @param freqDomain The frequency domain generated by FFT.
     */
    public void append(double[] freqDomain) {
        int[] freqPeaks = new int[interval_num];

        // The maximum amplitude and its frequency
        double max;
        int max_freq;

        // find the peak frequency in each interval
        for (int i = 0; i < interval_num; ++i) {
            max = 0;
            max_freq = freqRanges[i][0];
            for (int j = freqRanges[i][0]; j < freqRanges[i][1]; ++j) {
                if (freqDomain[j] > max) {
                    max = freqDomain[j];
                    max_freq = j;
                }
            }
            freqPeaks[i] = max_freq;
        }
        constel_data.add(freqPeaks);
    }

    /**
     * o(n)时间复杂度实现找出前三个最大值
     * 即算法导论上顺序统计量算法的具体实现
     *@param data 输入的数组
     * @param ordinal 序数*/
    public static double select(double[] data,int start,int end,int ordinal) {
        double globalMiddle;
        if(start > end) {
            throw new RuntimeException("the start must be less than end!");
        }
        else if(start == end) {
            return data[start];
        }
        else if(end - start <= 10) {
            getMiddleNumber(data,start,end);
            return data[start+ordinal-1];
        }
        else {
            int setNum;
            if(data.length%5==0) {
                setNum = data.length/5;
            }
            else {
                setNum = data.length/5+1;
            }
            double[] newData = new double[setNum];
            for (int i = 0; i < setNum-1; i++) {
                newData[i] = getMiddleNumber(data, i * 5, (i + 1) * 5);
            }
            newData[setNum-1] = getMiddleNumber(data, (setNum - 1) * 5, data.length);
            globalMiddle = select(newData,0,newData.length-1,newData.length/2);
            int k = partition(data,start,end,globalMiddle);
            int q = k-start;
            if(ordinal <= q) {
                return select(data,start,k,ordinal);
            }
            else {
                return select(data,k,end,q-ordinal);
            }
        }
    }

    /**
     * 来自快速排序的partition
     * @param data 输入的数组
     * @param privot 主元
     * @param start
     * @param end */
    private static int partition(double[] data,int start,int end,double privot) {
        int ordinal = start;
        double temp;
        for (int i = start; i <end ; i++) {
            if(data[i] > privot) {
                temp = data[ordinal];
                data[ordinal] = data[i];
                data[i] = temp;
                ordinal++;
            }
        }
        return ordinal;
    }

    /**
     * 对每一个得到的五个元素大小的新数组得到中位数
     * @param data 数组
     * @param start 对数组进行排序的初始元素下标，包括下标元素
     * @param end 对数组进行排序的末尾元素下标，不包括下标元素
     * @return 从开始到结束的中位数*/
    private static double getMiddleNumber(double[] data,int start,int end) {
        if(start == end) {
            return data[start];
        }
        else if(start>end) {
            throw new RuntimeException("the start must less than end!");
        }
        double temp;
        int i,j;
        for (i = start+1; i < end; i++) {
            temp = data[i];
            for (j = i-1; j >=start ; j--) {
                if(data[j] < temp) {
                    data[j+1] = data[j];
                    continue;
                }
                else {
                    break;
                }
            }
            data[j+1] = temp;
        }
        if((end-start)%2 == 0) {
            return data[start+(end-start)/2-1];
        }
        else {
            return data[(end-start-1)/2];
        }
    }

    /**
     * Generate fingerprints using Combinational Hash.
     * For each frequency peak, generate 6 fingerprints with its 6 successors.
     *
     * @return
     */
    public ArrayList<ShazamHash> combineHash() {
        if (constel_data.size() < 3)
            throw new RuntimeException("Too few frequency peaks");
        ArrayList<ShazamHash> hashes = new ArrayList<>();
        for (int i = 0; i < constel_data.size() - 2; ++i) {
            for (int k = 0; k < interval_num; ++k) {

                // "Combine" with all peak frequencies inside its next two frames.
                for (int j = 1; j <= 2; ++j) {
                    for (int kk = 1; kk < interval_num; ++kk) {
                        ShazamHash hash = new ShazamHash();
                        hash.f1 = (short) constel_data.get(i)[k];
                        hash.f2 = (short) constel_data.get(i + j)[kk];
                        hash.dt = (short) j;
                        hash.offset = i;
                        hash.id = id;
                        hash.caculateFinger_ID();
                        hashes.add(hash);
                    }
                }
            }
        }
        return hashes;
    }

   public void generate(double[] timeDomain) {
       int frames = timeDomain.length/4096;
       for (int i = 0; i < frames-1; i++) {
           append(FFT.fft(timeDomain,i*4096));
       }

   }
}
